1841E - Fill the Matrix - CodeForces Solution

#include <bits/stdc++.h>
using namespace std; 
typedef long long int ll;
#define MAXN 300010
const ll MOD = 1e9+7;

ll x[MAXN],par[MAXN],a[MAXN],si[MAXN], l[MAXN], r[MAXN];
vector<ll> posi[200004];
ll n,m,k;


ll findRep(ll u) {
    ll curr = u;
    while (par[curr] != curr) {
        curr = par[curr];
    }
    return curr;
}

void uni(ll u, ll v) {
    ll repU = findRep(u);
    ll repV = findRep(v);

    if (repU == repV) return;

    if (si[repU] > si[repV]) {
        par[repV] = repU;
        si[repU] += si[repV];
        l[repU] = min(l[repU], l[repV]);
        r[repU] = max(r[repU], r[repV]);
    } else {
        par[repU] = repV;
        si[repV] += si[repU];
        l[repV] = min(l[repU], l[repV]);
        r[repV] = max(r[repU], r[repV]);
    }


}
void solve() 
{
    cin >> n;
    for (ll i = 0; i < n; i++) {
        par[i] = i;
        si[i] = 1;
        l[i] = i;
        r[i] = i;
    }

    for (ll i= 0; i <= n; i++) {
        posi[i].clear();
    }
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> m;
    for (ll i = 0; i < n; i++) {
        posi[a[i]].push_back(i);
    }
    
   

    vector<ll> poss(n+1, 0);

    for (ll i = 0; i < n-1; i++) {
        if (a[i] == a[i+1]) {
            uni(i, i+1);
        }
    }


    for (ll i = 0; i < n; i++) {
        set<ll> reps;
        for (ll k = 0; k < posi[i].size(); k++) {
            reps.insert(findRep(posi[i][k]));
        }
        for (ll rep: reps) {
           // cout << i <<  " rep: " << rep << endl;
            ll leftLim = n;
            ll rightLim = n;
            if (l[rep] > 0) {
                leftLim = a[l[rep]-1];
            }
            if (r[rep] < n-1) {
                rightLim = a[r[rep]+1];
            }
            poss[si[rep]]+= min(leftLim, rightLim) - i;
            if (l[rep] > 0 && leftLim == min(leftLim, rightLim)) {
                uni(rep, l[rep]-1);
            }
            if (r[rep] < n-1 && rightLim == min(leftLim, rightLim)) {
                uni(rep, r[rep]+1);
            }
        }
    }
    /*

    for (ll i = 0; i <= n; i++) {
        cout << i << " " << poss[i] << endl;
    }
    cout << endl;*/
    


    ll rem = m;
    ll res = 0;
    for (ll i = n; i>= 1; i--) {
       // cout <<i << " f" <<res << endl;
        if (i * poss[i] < rem) {
            rem -= i*poss[i];
            res += (i-1)*poss[i];
        } else {
            ll canTake = rem/i;
            rem -= i*canTake;
            res += (i-1)*canTake;
            if (rem > 0) res += rem-1;
            cout <<  res << endl;
            return;
        }
    }



}


int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
 
	ll t;
	cin >> t;
	while (t--) {
        solve();
	}
	return EXIT_SUCCESS;
}